﻿#define  _CRT_SECURE_NO_WARNINGS


class Solution {
public:
	Node* copyRandomList(Node* head) {
		map<Node*, Node*> nodeMap;
		Node* copyhead = nullptr, * copytail = nullptr;
		Node* cur = head;
		while (cur)
		{
			if (copytail == nullptr)
			{
				copyhead = copytail = new Node(cur->val);
			} 
				else
			{
			copytail->next = new Node(cur->val);
			copytail = copytail->next;
			} 
				// 原节点和拷⻉节点map kv存储
				nodeMap[cur] = copytail;
			cur = cur->next;
		} 
			// 处理random
		cur = head;
		Node* copy = copyhead;
		while (cur)
		{
			if (cur->random == nullptr)
			{
				copy->random = nullptr;
			} 
			else
			{
				copy->random = nodeMap[cur->random];
			} 
			cur = cur->next;

			copy = copy->next;
		} 
			return copyhead;
	}
};